package dp;

/**
 * 188. 买卖股票的最佳时机4
 * 给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 */

public class BestTimeToSellAndBuyStock_188 {
    // 动态规划
    public int maxProfit(int k, int[] prices) {
        // 最多可以进行k次操作，定义dp数组dp[i][j][2]，j < k
        // dp[i][j][0]表示第i天进行了j次买入，j-1次卖出的最大利润
        // dp[i][j][1]表示第i天进行了j次买入，j次卖出的最大利润

        if (prices.length == 0) {
            return 0;
        }

        // 以后这种涉及到天数的问题，创建数组时+1
        int[][][] dp = new int[prices.length][k + 1][2];
        // 定义base case
        for (int j = 1; j < k + 1; j++) {
            dp[0][j][0] = -prices[0];
            dp[0][j][1] = 0;
        }

        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j < k + 1; j++) {
                // 在第i天进行了j次买入，j-1次卖出，1. 之前操作的，今天未操作；2. 之前进行了j-1次买入，j-1次卖出，今天买入
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j - 1][1] - prices[i]);
                // 在第i天进行了j次买入，j次卖出，1. 之前操作的，今天未操作；2. 之前进行了j次买入，j-1次卖出，今天卖出
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j][0] + prices[i]);
            }
        }
        return dp[prices.length - 1][k][1];
    }
}
